package top.carrotguo.sorting;

/**
 * 归并排序
 * @Author: Carrot
 * @Mail: 1053155183carrot@gmail.com
 * @Date: Created in 16:39 2018-05-22
 */
public class MergeSort {

    private int[] data;

    public MergeSort(int[] data){
        this.data = data;
    }

    public void printData(){
        if (data != null) {
            for (int i=0; i<data.length; i++) {
                System.out.print(data[i]+" ");
            }
        }

    }

    public void sort(int lo,int hi){
        if (hi-lo<2) {
            return;     //单个元素不需要再分割
        }
        int mi = (lo+hi)/2;
        sort(lo,mi);
        sort(mi,hi);
        //归并
        merge(lo,mi,hi);
    }

    private void merge(int lo, int mi, int hi){
        //b数组长度
        int lb = mi-lo;
        //c数组长度
        int lc = hi-mi;
        int[] B = new int[lb];
        int[] C = new int [lc];
        //复制数组前半段至B中以防归并过程被覆盖
        System.arraycopy(data,lo,B,0,lb);
        System.arraycopy(data,mi,C,0,lc);
        //当前指向前半段数组B的下标
        int k=0;
        //当前指向后半段数组C的下标
        int j=0;
        for (int i=lo; (k<lb)||(j<lc);) {
            if ((k<lb) && (lc<=j || B[k]<=C[j])) {
                data[i++] = B[k++];
            }
            if ((j<lc) && (lb<=k || C[j]<B[k])) {
                data[i++] = C[j++];
            }
        }
    }

    public static void main(String[] args){
        MergeSort sort = new MergeSort(new int[]{2,7,55,4,8,1,6});
        sort.sort(0,7);
        sort.printData();
    }
}
